一.强连通分量的定义
在有向图G中,如果两个顶点vi,vj间(vi!=vj)有一条从vi到vj的有向路径,同时还有一条从vj到vi的有向路径(即两点互相可达),则称两个顶点强连通。如果有向图G的每两个顶点都强连通,称G是一个强连通图。有向图的极大强连通子图,称为强连通分量。
一个有向图是强连通的,当且仅当G中有一个回路,它至少包含每个节点一次。
二.实现算法
1.Kosaraju算法
1.引入

我们先来看这样一张图,这是一个有两个强联通分量的一个有向图。如果我们对这个有向图进行遍历,我们如果是从A这边开始,那么只需要一个DFS就可以搜索完整个有向图,但我们如果从B这边开始,则需要两个DFS。很显然,我们这个有向图有两个强联通分量,那么,我们选择合适的起始位置(B这边的点)才能得到正确的答案。
Kosaraju算法就是寻找合适的起点,记录搜索次数。
2.算法流程
1、随意给起点进行DFS,每次在DFS回溯的过程中进行标记,得到一个后序遍历的顺序的表。
2、对原图G进行反向,得到反图R,按照步骤1中得到的表,从后往前进行DFS遍历。
3、在步骤2中,使用了多少次的DFS,就有多少个强联通分量。
代码如下:(s为后续遍历表)
void dfs1( int u ) {
vis[ u ] = 1;
for( int i = 0 ; i < Graph[ u ].size( ) ; i ++ ) {
int v = Graph[ u ][ i ];
if( !vis[ v ] ) dfs1( v );
}
s.push_back( u );
}
void dfs2( int u ) {
belong[ u ] = k;
for( int i = 0 ; i < dis_Graph[ u ].size( ) ; i ++ ) {
int v = Graph[ u ][ i ];
if( !belong[ v ] ) dfs2( v );
}
}
void Kosaraju() {
for( int i = 1 ; i <= n ; i ++ )
if( !vis[ i ] ) dfs( i );
for( int i = n - 1 ; i >= 0 ; i -- ) {
if( !belong[ s[ i ] ] ) {
k++;
dfs2( s[ i ] );
}
}
}
3.复杂度分析
两次dfs遍历,复杂度
2.tarjan算法
1.引入
Tarjan算法是基于DFS的算法,每个强连通分量为搜索树中的一棵子树。搜索时,把当前搜索树中未处理的节点加入一个堆栈,回溯时可以判断栈顶到栈中的节点是否为一个强连通分量。
2.算法流程
定义为节点u的搜索次序编号(序),为u或u的子树能追溯到的最早的栈中节点。初始化时,编号。
将搜索到的u压入栈中,枚举所有u出去的边。
1.如果v没有被访问,那么访问v,并在回溯时,计算;
2.如果v在栈内,说明当前已经构成一个环,那么.
3.当u没有下一个节点可以搜索时,判断是否等于,如果相等,则将栈顶元素v退栈,直到退出u为止,这次退出的所有点即为一个连通分量(它们构成了一个环)。注意,当u=v时,也要退栈,此时u本身是一个强连通分量。
代码如下:
void Tarjan( int u ) {
dfn[ u ] = low[ u ] = ++ depth;
is[ u ] = 1;
S.push( u );
for( int i = 0 ; i < Graph[ u ].size() ; i ++ ) {
int v = Graph[ u ][ i ];
if( !dfn[ v ] ) {
Tarjan( v );
low[ u ] = Min( low[ u ] , low[ v ] );
}
else if( is[ v ] ) {
low[ u ] = Min( low[ u ] , dfn[ v ] );
}
}
if( dfn[ u ] == low[ u ] ) {
int v;
num ++;
do{
v = S.top( );
S.pop( );
is[ v ] = 0;
}while( u != v );
}
}
3.复杂度分析
只需一次dfs遍历,复杂度
三.例题
1.HDU P1269 (迷宫城堡)
模板题,不多讲,判断强连通分量个数是否为一即可。
注意在多组数据时将各种量清空。代码如下:
#include <cstdio>
#include <vector>
#include <stack>
#include <cstring>
using namespace std;
const int MAXN = 10005;
int n,m,a,b,depth,num;
int dfn[ MAXN + 5 ] , low[ MAXN + 5];
stack< int > S;
vector< int > Graph[ MAXN + 5];
bool is[ MAXN + 5 ];
int Min( int x , int y ) {
return x < y ? x : y;
}
void Tarjan( int u ) {
dfn[ u ] = low[ u ] = ++ depth;
is[ u ] = 1;
S.push( u );
for( int i = 0 ; i < Graph[ u ].size() ; i ++ ) {
int v = Graph[ u ][ i ];
if( !dfn[ v ] ) {
Tarjan( v );
low[ u ] = Min( low[ u ] , low[ v ] );
}
else if( is[ v ] ) {
low[ u ] = Min( low[ u ] , dfn[ v ] );
}
}
if( dfn[ u ] == low[ u ] ) {
int v;
num ++;
do{
v = S.top( );
S.pop( );
is[ v ] = 0;
}while( u != v );
}
}
int main( ) {
while( 1 ) {
scanf("%d %d",&n,&m);
if( n == 0 && m == 0 )
return 0;
while( !S.empty() )
S.pop();
for( int i = 1 ; i <= MAXN ; i ++ )
Graph[ i ].clear( );
for( int i = 1 ; i <= m ; i ++ ) {
scanf("%d %d",&a,&b);
Graph[ a ].push_back( b );
}
depth = num = 0;
memset( dfn , 0 , sizeof( dfn ) );
memset( low , 0 , sizeof( low ) );
memset( is , 0 , sizeof( is ) );
for( int i = 1 ; i <= n ; i ++ )
if( !dfn[ i ] ) Tarjan( i );
if( num == 1 )
printf("Yes\n");
else
printf("No\n");
}
return 0;
}
2.HDU P1827 (Summer Holiday)
首先建图,求出所有的强连通分量,并进行缩点。缩点的同时,找出所有分量的入度,如果入度为0,那么消耗就为这个强连通分量内的所有人的花费最少的那个人,因为只需通知花费最小的就可以通知整个分量。如果不为0,说明有其他分量可以通知该分量,就没有花费。
代码如下:
#include <cstdio>
#include <cstring>
#include <vector>
#include <stack>
using namespace std;
const int MAXN = 1000;
int n,m,a,b,cost[ MAXN + 5 ];
vector< int > Graph[ MAXN + 5 ];
vector< int > lit_Graph[ MAXN + 5 ];
stack< int > S;
int dfn[ MAXN + 5 ] , low[ MAXN + 5 ] , depth;
int belong[ MAXN + 5 ] , lit_cost[ MAXN + 5 ] , num;
bool is[ MAXN + 5 ];
int In_num[ MAXN + 5 ];
int Min( int x , int y ) {
return x < y ? x : y;
}
void Tarjan( int u ) {
dfn[ u ] = low[ u ] = ++ depth;
S.push( u ) ; is[ u ] = 1;
for( int i = 0 ; i < Graph[ u ].size() ; i ++ ) {
int v = Graph[ u ][ i ];
if( !dfn[ v ] ) {
Tarjan( v );
low[ u ] = Min( low[ u ] , low[ v ] );
}
else if( is[ v ] )
low[ u ] = Min( low[ u ] , dfn[ v ] );
}
if( dfn[ u ] == low[ u ] ) {
int v;
num ++;
do{
v = S.top( );
S.pop( );
is[ v ] = 0;
belong[ v ] = num;
lit_cost[ num ] = Min( lit_cost[ num ] , cost[ v ] );
}while( u != v );
}
}
void Memset( ) {
num = depth = 0;
for( int i = 1 ; i <= MAXN ; i ++ )
Graph[ i ].clear( ) , lit_Graph[ i ].clear( );
while( !S.empty() ) S.pop();
memset( lit_cost , 0x3f , sizeof( lit_cost ) );
memset( dfn , 0 , sizeof( dfn ) );
memset( low , 0 , sizeof( low ) );
memset( belong , 0 , sizeof( belong ) );
memset( is , 0 , sizeof( is ) );
memset( In_num , 0 , sizeof( In_num ) );
}
int main( ) {
while( ~scanf("%d %d",&n,&m) ) {
Memset( );
for( int i = 1 ; i <= n ; i ++ )
scanf("%d",&cost[ i ]);
for( int i = 1 ; i <= m ; i ++ ) {
scanf("%d %d",&a,&b);
Graph[ a ].push_back( b );
}
for( int i = 1 ; i <= n ; i ++ )
if( !dfn[ i ] ) Tarjan( i );
for( int i = 1 ; i <= n ; i ++ )
for( int j = 0 ; j < Graph[ i ].size( ) ; j ++ )
if( belong[ i ] != belong[ Graph[ i ][ j ] ] ) {
lit_Graph[ belong[ i ] ].push_back( belong[ Graph[ i ][ j ] ] );
In_num[ belong[ Graph[ i ][ j ] ] ] ++;
}
int Ans = 0 , tot = 0;
for( int i = 1 ; i <= num ; i ++ ) {
if( In_num[ i ] == 0 )
Ans += lit_cost[ i ];
else
tot ++;
}
printf("%d %d\n",num - tot,Ans);
}
return 0;
}
3.HDU P2767 (Proving Equivalences)
先求出k个强连通分量,并记录这些强连通分量中,入度为0和出度为0的个数,最终要添加的边数就是这两个中的最大值。
4.HDU P3861 ( The King’s Problem)
首先对强连通分量进行缩点,得到一个有向无环图(DAG)图,最后就是一个在一个DAG图上求最小路径覆盖,直接用一个二分图匹配即可。
5.POJ P3114 (Countries in War )
首先对强连通分量进行缩点,得到一个有向图,然后跑一遍最短路即可,建议用spfa。
代码如下:
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <cstring>
using namespace std;
const int MAXN = 1000;
int n,m,x,y,z,t;
struct node{
int v,w;
node(){}
node( int V , int W ) {
v = V;
w = W;
}
};
vector< node > Graph[ MAXN + 5 ] , lit_Graph[ MAXN + 5 ];
stack< int > s;
int Max( int x , int y ) {
return x > y ? x : y;
}
int Min( int x , int y ) {
return x < y ? x : y;
}
int dfn[ MAXN + 5 ] , low[ MAXN + 5 ] , belong[ MAXN + 5 ];
int num , depth;
bool is[ MAXN + 5 ];
void Tarjan( int u ) {
dfn[ u ] = low[ u ] = ++ depth;
s.push( u );
is[ u ] = 1;
for( int i = 0 ; i < Graph[ u ].size( ) ; i ++ ) {
int v = Graph[ u ][ i ].v;
if( !dfn[ v ] ) {
Tarjan( v );
low[ u ] = Min( low[ u ] , low[ v ] );
}
else if( is[ v ] )
low[ u ] = Min( low[ u ] , dfn[ v ] );
}
if( dfn[ u ] == low[ u ] ) {
int v;
num ++;
do{
v = s.top( );
s.pop( ) , is[ v ] = 0;
belong[ v ] = num;
}while( u != v );
}
}
int dis[ MAXN + 5 ];
bool vis[ MAXN + 5 ];
void spfa( int s ) {
queue< int > Q;
memset( dis , 0x3f , sizeof( dis ) );
memset( vis , 0 , sizeof( vis ) );
dis[ s ] = 0 , vis[ s ] = 1;
Q.push( s );
while( !Q.empty( ) ) {
int u = Q.front( );
vis[ u ] = 0;
Q.pop( );
for( int i = 0 ; i < lit_Graph[ u ].size( ) ; i ++ ) {
int v = lit_Graph[ u ][ i ].v , w = lit_Graph[ u ][ i ].w;
if( dis[ u ] + w < dis[ v ] ) {
dis[ v ] = dis[ u ] + w;
if( !vis[ v ] )
Q.push( v ) , vis[ v ] = 1;
}
}
}
}
void Memset( ) {
depth = num = 0;
memset( is , 0 , sizeof( is ) );
memset( dfn , 0 , sizeof( dfn ) );
memset( low , 0 , sizeof( low ) );
memset( belong , 0 , sizeof( belong ) );
for( int i = 1 ; i <= MAXN ; i ++ )
Graph[ i ].clear( ) , lit_Graph[ i ].clear( );
while( !s.empty( ) ) s.pop( );
}
int main( ) {
while( scanf("%d %d",&n,&m) && n ) {
Memset( );
for( int i = 1 ; i <= m ; i ++ ) {
scanf("%d %d %d",&x,&y,&z);
Graph[ x ].push_back( node( y , z ) );
}
for( int i = 1 ; i <= n ; i ++ )
if( !dfn[ i ] ) Tarjan( i );
for( int i = 1 ; i <= n ; i ++ )
for( int j = 0 ; j < Graph[ i ].size( ) ; j ++ )
if( belong[ i ] != belong[ Graph[ i ][ j ].v ] )
lit_Graph[ belong[ i ] ].push_back( node( belong[ Graph[ i ][ j ].v ] , Graph[ i ][ j ].w ) );
scanf("%d",&t);
while( t -- ) {
scanf("%d %d",&x,&y);
x = belong[ x ] , y = belong[ y ];
spfa( x );
if( dis[ y ] == 0x3f3f3f3f )
printf("Nao e possivel entregar a carta\n");
else
printf("%d\n",dis[ y ]);
}
printf("\n");
}
return 0;
}